#define _CRT_SECURE_NO_WARNINGS	

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

int* Get_Next(const char* sub)
{
    assert(sub);

    int len = strlen(sub);

    int* next = (int*)malloc(sizeof(int) * len);
    int* nextval = (int*)malloc(sizeof(int) * len);

    if (!next)
        exit(EXIT_FAILURE);

    next[0] = -1, next[1] = 0;

    int i = 1, j = 0;
    while (i + 1 < len)
    {
        if (j == -1 || sub[i] == sub[j])
        {
            j++;
            i++; 
            next[i] = j;
        }
        else
            j = next[j];
    }

    nextval[0] = -1;

    for (int i = 1; i < len; i++)
    {
        if (sub[i] == sub[next[i]])
            nextval[i] = nextval[next[i]];
        else
            nextval[i] = next[i];
    }

    free(next);
    next = NULL;

    return nextval;
}

int KMP(const char* des, const char* sub, int pos)
{
    assert(des && sub);
    int* next = Get_Next(sub);

    int len_des = strlen(des), len_sub = strlen(sub);

    int i = pos, j = 0;
    while (i < len_des && j < len_sub)
    {
        if (j == -1 || des[i] == sub[j])
            i++, j++;
        else
            j = next[j];
    }

    if (j < strlen(sub))
        return -1;

    return i - j;
}


int main()
{
    int* next = Get_Next("AAAAB");
    for (int i = 0; i < 5; i++)
        printf("%d", next[i]);
    return 0;
}